package heapSort;

/**
 *    堆排序代码实现
 *    时间复杂度: O(N * log n)
 *    空间复杂度: O(1)
 *    稳定性: 不稳定
 */

//堆排序：升序建立大根堆-》交换-》调整
public class MyHeapSort {

   public static void heapSort(int[] array) {
      createBigHeap(array);

      int end = array.length - 1;
      while(end >= 0) {
         swap(array,0,end);
         shiftDown(array,0,end);
         end--;
      }

   }

   //建立大根堆
   private static void createBigHeap(int[] array) {
      for (int parent =(array.length - 2) >>> 1 ; parent >= 0; parent--) {
         shiftDown(array,parent, array.length);
      }
   }
   //向下调整
   private static void shiftDown(int[] array,int parent,int len) {
      int child = (parent << 1) + 1;

      while(child < len) {
         if(child+1 < len && array[child] < array[child+1]) {
            child++;
         }
         if(array[child] > array[parent]) {
            swap(array,child,parent);
            parent = child;
            child = (parent << 1) + 1;
         }else {
            break;
         }
      }
   }
   //交换
   private static void swap(int[] array,int child,int parent) {
      int tmp = array[child];
      array[child] = array[parent];
      array[parent] = tmp;
   }

}
